/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sort-colors
   @Language: C++
   @Datetime: 16-02-09 08:34
   */

// Method 1, traversal twice
class Solution{
public:
	/**
	 * @param nums: A list of integer which is 0, 1 or 2 
	 * @return: nothing
	 */    
	void sortColors(vector<int> &A) {
		// write your code here
		int C[3] = {0,0,0};		// record each color count
		for(int i=A.size(); i; ++C[A[--i]]);
		for(int c=0, i=0; c<3; ++c)
			for(; C[c]--; A[i++]=c);
	} 
};

// Method 2, 3 partitions
class Solution {
public:
	void sortColors(vector<int>& nums) {
		for(int zero=-1, i=0, two=nums.size(); i<two; ++i)
			if(nums[i]==0) swap(nums[++zero],nums[i]);
			else if(nums[i]==2) swap(nums[--two],nums[i--]);
	}
};
